package junior.回溯法;

public class 背包01 {
    static int N = 5; //商品数量
    static int C = 7; //背包容量
    //      初始化数据(注意适配边界)
    static int[] weight = {1  ,2  ,3  ,4  ,5 };  // 商品重量
    static int[]  price = {2  ,4  ,5  ,6  ,7};  // 商品价格
    static int[] stack = new int[100000]; // 构造解空间
    static int[] result = new int[10000]; // 保存结果
    static int top = 0, total=0, maxPrice = 0,tempPrice = 0,tempWeight;

    public static void main(String[] args) {
        fun(0);
        System.out.println("解空间个数: "+total);
        System.out.println("最大价值: "+maxPrice);
        showResult(result);
    }
    public static void fun(int n){
        if(n == N){
            for (int i = 0; i < top; i++) {
                if(stack[i] == 1){
                    tempPrice += price[i];
                    tempWeight += weight[i];
                }
            }
            if(tempWeight <= C && maxPrice <= tempPrice) {
                maxPrice = tempPrice;
                for (int i = 0; i < top; i++) {
                    result[i] = stack[i];
                }
            }
            tempPrice = 0;
            tempWeight = 0;
            total++;
            return;
        }
        for (int i = 0; i <= 1; i++) {
            stack[top++] = i;
            fun(n+1);
            top--;
        }
    }
    public static void showResult(int[] result){
        System.out.println();
        System.out.println("全部的商品为:");
        System.out.print("商品重量: ");
        for (int i = 0; i < N; i++) {
            System.out.print(weight[i]+"\t");
        }
        System.out.println();
        System.out.print("商品价格: ");
        for (int i = 0; i < N; i++) {
            System.out.print(price[i]+"\t");
        }
        System.out.println();
        System.out.print("商品编号: ");
        for (int i = 0; i < N; i++) {
            System.out.print(i+"\t");
        }
        System.out.println();
        System.out.println();
        System.out.println("装入的商品为:");
        for (int i = 0; i < N; i++) {
            if(result[i] == 1){
                System.out.println("商品编号: "+i+"\t\t商品重量: "+weight[i]+"\t\t商品价格: "+price[i]);
            }
        }
    }
}
